/*
 * Copyright (c) 2009-2010 HIT Microelectronic Center
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Authors: Gou Pengfei
 *          Jin Yinghan
 *
 * Date:    Dec. 2009
 *          Nov. 2010
 *          Dec. 2010
 *
 */

#include <map>

#include "cpu/edge/inst_queue.hh"
#include "cpu/edge/mem_dep_unit.hh"

#include "params/DerivEdgeCPU.hh"

template <class MemDepPred, class Impl>
EdgeMemDepUnit<MemDepPred, Impl>::EdgeMemDepUnit()
    : loadBarrier(false), loadBarrierSN(0), storeBarrier(false),
      storeBarrierSN(0), iqPtr(NULL)
{
}

template <class MemDepPred, class Impl>
EdgeMemDepUnit<MemDepPred, Impl>::EdgeMemDepUnit(DerivEdgeCPUParams *params)
    : _name(params->name + ".memdepunit"),
      loadBarrier(false),
      loadBarrierSN(0), storeBarrier(false),
      storeBarrierSN(0), iqPtr(NULL),
      isPerfect(false)
{
}

template <class MemDepPred, class Impl>
EdgeMemDepUnit<MemDepPred, Impl>::~EdgeMemDepUnit()
{
    memDepHash.clear();

    instsToReplay.clear();

    for (ThreadID tid = 0; tid < Impl::MaxThreads; tid++) {
        instList[tid].clear();
    }

#ifdef DEBUG
    assert(MemDepEntry::memdep_count == 0);
#endif
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::init(DerivEdgeCPUParams *params, ThreadID tid)
{
    DPRINTF(EdgeMemDepUnit, "Creating EdgeMemDepUnit %i object.\n",tid);

    if (params->memDepMode == "Perfect") {
        isPerfect = true;
        DPRINTF(EdgeMemDepUnit, "This is a perfect EdgeMemDepUnit.\n");

        if (!params->preExecuteMode) {
            panic("Perfect EdgeMemDepUnit only works in preExecuteMode.\n");
        }

    } else {
        isPerfect = false;
    }

    _name = csprintf("%s.memDep%d", params->name, tid);
    id = tid;
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::regStats()
{
    insertedLoads
        .name(name() + ".insertedLoads")
        .desc("Number of loads inserted to the mem dependence unit.");

    insertedStores
        .name(name() + ".insertedStores")
        .desc("Number of stores inserted to the mem dependence unit.");

    conflictingLoads
        .name(name() + ".conflictingLoads")
        .desc("Number of conflicting loads.");

    conflictingStores
        .name(name() + ".conflictingStores")
        .desc("Number of conflicting stores.");
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::switchOut()
{
    assert(instList[0].empty());
    assert(instsToReplay.empty());
    assert(memDepHash.empty());
    // Clear any state.
    for (int i = 0; i < Impl::MaxThreads; ++i) {
        instList[i].clear();
    }
    instsToReplay.clear();
    memDepHash.clear();
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::takeOverFrom()
{
    // Be sure to reset all state.
    loadBarrier = storeBarrier = false;
    loadBarrierSN = storeBarrierSN = 0;
    //depPred.clear();
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::setIQ(IQ *iq_ptr)
{
    iqPtr = iq_ptr;
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::insert(DynInstPtr &inst)
{
    ThreadID tid = inst->threadNumber;

    MemDepEntryPtr inst_entry = new MemDepEntry(inst);

    uint64_t insert_key = inst->staticInst->getLSID() |
                          (inst->getBlockID() << 5);

    // Add the MemDepEntry to the hash.
    memDepHash.insert(std::pair<uint64_t, MemDepEntryPtr>(insert_key, inst_entry));

    DPRINTF(EdgeMemDepUnit, "Adding key %x, PC @%#x, [Bid:%lli][LSID:%i]\n",
            insert_key,
            inst->readPC(),
            inst->getBlockID(),
            inst->staticInst->getLSID() );

#ifdef DEBUG
    MemDepEntry::memdep_insert++;
#endif

    instList[tid].push_back(inst);

    inst_entry->listIt = --(instList[tid].end());

    std::vector<uint64_t> keys;

    if (inst->isLoad() && loadBarrier) {
        panic("Not supportted inst: load barrier.\n");
    } else if (inst->isStore() && storeBarrier) {
        panic("Not supportted inst: store barrier.\n");
    } else {
        // For normal mem insts, last store in LSID
        // sequence could be the producer.
        //
        // Only loads should respect the memory dependence. Dependence
        // of stores will be guaranteed by block-atomic commit and
        // LSID-order writeback.
        //
        // @todo: Memory predictor should be put here.
        if (inst->isLoad()) {
            findLastStores(inst, keys, tid);
        }
    }

    MemDepEntryPtr store_entry = NULL;

    MemDepHashIt pos;

    if (inst->isStore() || keys.size() == 0) {

        DPRINTF(EdgeMemDepUnit, "No dependency for inst PC "
                "%#x [Bid:%lli][Iid:%lli][LSID:%i].\n", 
                inst->readPC(),
                inst->getBlockID(),
                inst->getInstID(),
                inst->staticInst->getLSID());

        inst_entry->memDepReady = true;

        if (inst->readyToIssue()) {
            inst_entry->opsReady = true;
            moveToReady(inst_entry);
        }

    } else {

        for (int idx = 0; idx < keys.size(); idx++) {

            uint64_t key = keys[idx];

            DPRINTF(EdgeMemDepUnit, "Find a prior store, key = %#x.\n", key);

            int dep_count = 0;
            // If there is a producing store, try to find the entry.
            for (pos = memDepHash.lower_bound(key);
                 pos != memDepHash.upper_bound(key);
                 ++pos) {

                DPRINTF(EdgeMemDepUnit, "Searching for producer.\n");

                if (pos != memDepHash.end()) {
                    store_entry = (*pos).second;
                    DPRINTF(EdgeMemDepUnit, "Producer found.\n");
                }

                // We are supposed to find the store entry.
                if (store_entry) {

                    // We are in perfect mode, so we can check the
                    // dependents here.
                    // Moreover, we can check the dependents only if
                    // this block is in correct path. As blocks
                    // in wrong path will be squashed and they are not
                    // executed in fetch stage, they will respect the
                    // conservative memory dependence policy.
                    if (isPerfect && inst->isBlockInCorrectPath()) {
                        if (!checkDependent(inst, store_entry->inst)) {
                            DPRINTF(EdgeMemDepUnit, "No dependent found.\n");
                            continue;
                        }
                    }

                    // Otherwise make the instruction dependent on the store.
                    DPRINTF(EdgeMemDepUnit, "Adding to dependency list: "
                            "inst[Bid:%lli][Iid:%lli][LSID:%i] @%#x is dependent on"
                            " [Bid:%lli][Iid:%lli][LSID:%i][key:%x].\n",
                            inst->getBlockID(),
                            inst->getInstID(),
                            inst->staticInst->getLSID(),
                            inst->readPC(),
                            store_entry->inst->getBlockID(),
                            store_entry->inst->getInstID(),
                            store_entry->inst->staticInst->getLSID(),
                            key);
                    
                    if (inst->readyToIssue()) {
                       inst_entry->opsReady = true;
                    }

                    // Clear the bit saying this instruction can issue.
                    inst->clearCanIssue();

                    DPRINTF(EdgeMemDepUnit, "Size of dependInsts of this"
                            " store entry is %i\n",
                            store_entry->dependInsts.size());

                    // Add this instruction to the list of dependents.
                    store_entry->dependInsts.push_back(inst_entry);

                    dep_count++;

                    if (inst->isLoad()) {
                        ++conflictingLoads;
                    } else {
                        ++conflictingStores;
                    }

                } else {
                    // Store_entry is supposed to be existed.
                    assert(store_entry);
                }
            }

            if (pos == memDepHash.lower_bound(key)) {
                assert(0 && "we are supposed to find the entry");
            }

            if (dep_count > 0) {
                // Set the counter of how many stores this load are dependent
                // on. Each key correspond to one dependence because only
                // one of these instructions with the same key will
                // execute.
                inst_entry->loadDepCount++;
            }
        }

        // If we're in perfect mode and there is no dependents for
        // this instruction, which means the pre-execute model
        // tell us that this load won't dependent upon any of its
        // prior stores. As a result, we can say the memory
        // dependence has been resolved for this load.
        if (isPerfect && inst->isBlockInCorrectPath() &&
            inst_entry->loadDepCount == 0) {

            DPRINTF(EdgeMemDepUnit, "No dependency for inst PC "
                    "%#x [Bid:%lli][Iid:%lli][LSID:%i].\n", 
                    inst->readPC(),
                    inst->getBlockID(),
                    inst->getInstID(),
                    inst->staticInst->getLSID());

            inst_entry->memDepReady = true;

            if (inst->readyToIssue()) {
                inst_entry->opsReady = true;
                moveToReady(inst_entry);
            }
        }
    }

    if (inst->isStore()) {
        ++insertedStores;
    } else if (inst->isLoad()) {
        ++insertedLoads;
    } else {
        panic("Unknown type! (most likely a barrier).");
    }
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::insertNonSpec(DynInstPtr &inst)
{
    panic("Unimplemented func: insertNonSpec.\n");
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::insertBarrier(DynInstPtr &barr_inst)
{
    InstSeqNum barr_sn = barr_inst->staticInst->getLSID() | (barr_inst->getBlockID() << 5);
    // Memory barriers block loads and stores, write barriers only stores.
    if (barr_inst->isMemBarrier()) {
        loadBarrier = true;
        loadBarrierSN = barr_sn;
        storeBarrier = true;
        storeBarrierSN = barr_sn;
        DPRINTF(EdgeMemDepUnit, "Inserted a memory barrier\n");
    } else if (barr_inst->isWriteBarrier()) {
        storeBarrier = true;
        storeBarrierSN = barr_sn;
        DPRINTF(EdgeMemDepUnit, "Inserted a write barrier\n");
    }

    ThreadID tid = barr_inst->threadNumber;

    MemDepEntryPtr inst_entry = new MemDepEntry(barr_inst);

    // Add the MemDepEntry to the hash.
    memDepHash.insert(
        std::pair<uint64_t, MemDepEntryPtr>(barr_sn, inst_entry));
#ifdef DEBUG
    MemDepEntry::memdep_insert++;
#endif

    // Add the instruction to the instruction list.
    instList[tid].push_back(barr_inst);

    inst_entry->listIt = --(instList[tid].end());
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::opsReady(DynInstPtr &inst)
{
    DPRINTF(EdgeMemDepUnit, "Marking operands as ready for "
            "instruction PC %#x [sn:%lli].\n",
            inst->readPC(), inst->seqNum);

    MemDepEntryPtr inst_entry = findInHash(inst);

    if (!inst_entry) {
        warn("No entry found when tried to mark a"
                " memref as opsReady! Maybe this entry had been"
                " completed before.\n");
        return;
    }

    inst_entry->opsReady = true;

    if (inst_entry->memDepReady) {
        DPRINTF(EdgeMemDepUnit, "Instruction has its memory "
                "dependencies resolved, adding it to the ready list.\n");

        moveToReady(inst_entry);
    } else {
        DPRINTF(EdgeMemDepUnit, "Instruction still waiting on "
                "memory dependency.\n");
    }
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::nonSpecInstReady(DynInstPtr &inst)
{
    panic("Unimplemented func: nonSpecInstReady().\n");
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::reschedule(DynInstPtr &inst)
{
    instsToReplay.push_back(inst);
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::replay()
{
    DynInstPtr temp_inst;

    // For now this replay function replays all waiting memory ops.
    while (!instsToReplay.empty()) {
        temp_inst = instsToReplay.front();

        MemDepEntryPtr inst_entry = findInHash(temp_inst);

        if (inst_entry) {
            DPRINTF(EdgeMemDepUnit, "Replaying mem instruction PC %#x "
                    "[Bid:%lli][Iid:%lli][LSID:%i].\n",
                    temp_inst->readPC(), 
                    temp_inst->getBlockID(),
                    temp_inst->getInstID(),
                    temp_inst->staticInst->getLSID());

            moveToReady(inst_entry);

            instsToReplay.pop_front();
        } else {
            assert(0 && "Can not find entry when replay memrefs.\n");
        }
    }
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::completed(DynInstPtr &inst)
{
    DPRINTF(EdgeMemDepUnit, "Completed mem instruction PC %#x "
            "[Bid:%lli][Iid:%i].\n",
            inst->readPC(), 
            inst->getBlockID(),
            inst->getInstID());

    ThreadID tid = inst->threadNumber;

    MemDepHashIt pos;

    uint64_t key = inst->staticInst->getLSID() | (inst->getBlockID() << 5);
    
    DPRINTF(EdgeMemDepUnit, "Deleting key:%x\n", key);
    
    for (pos = memDepHash.lower_bound(key);
         pos != memDepHash.upper_bound(key);
         ) {

        assert(pos != memDepHash.end());

        DPRINTF(EdgeMemDepUnit,"Clear memory dependence entry"
                " of inst[Tid:%i][Bid:%lli][Iid:%i].\n",
                (*(pos->second->listIt))->threadNumber,
                (*(pos->second->listIt))->getBlockID(),
                (*(pos->second->listIt))->getInstID());

        instList[tid].erase((*pos).second->listIt);

        (*pos).second = NULL;

        memDepHash.erase(pos++);
        #ifdef DEBUG
        MemDepEntry::memdep_erase++;
        #endif
    }

    return;
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::completeBarrier(DynInstPtr &inst)
{
    panic("Unimplemented func: completeBarrier.\n");
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::wakeDependents(DynInstPtr &inst)
{
    // Only stores and barriers have dependents.
    if (!inst->isStore() && !inst->isMemBarrier() && !inst->isWriteBarrier()) {
        return;
    }

    MemDepEntryPtr inst_entry = findInHash(inst);

    if (!inst_entry) {
        assert(0 && "Can not find entry when trying"
                " to wake dependents of memrefs.\n");
    }

    if (inst->isNullified()) {

        DPRINTF(EdgeMemDepUnit,"Mem inst[Bid:%lli][Iid:%lli][LSID:%i]"
                " is nullified",
                inst->getBlockID(),
                inst->getInstID(),
                inst->staticInst->getLSID());
    }

    for (int i = 0; i < inst_entry->dependInsts.size(); ++i) {
        MemDepEntryPtr woken_inst = inst_entry->dependInsts[i];

        if (!woken_inst->inst) {
            // Potentially removed mem dep entries could be on this list
            continue;
        }

        if (woken_inst->issued) {
            DPRINTF(EdgeMemDepUnit, "Dependent inst[Bid:%lli][LSID:%i]"
                    " has been issued, "
                    "no need to wake it up again.\n",
                    woken_inst->inst->getBlockID(),
                    woken_inst->inst->staticInst->getLSID());
            continue;
        }

        DPRINTF(EdgeMemDepUnit, "Waking up a dependent inst, "
                "[Bid:%lli][Iid:%lli][LSID:%i].\n",
                woken_inst->inst->getBlockID(),
                woken_inst->inst->getInstID(),
                woken_inst->inst->staticInst->getLSID() );

        assert(woken_inst->inst->isLoad());
        assert(woken_inst->loadDepCount > 0); 

        woken_inst->loadDepCount--;

        DPRINTF(EdgeMemDepUnit, "Dependence count for this"
                " entry is %i\n", 
                woken_inst->loadDepCount);

        if (woken_inst->loadDepCount == 0) {
            if (woken_inst->opsReady && 
                !woken_inst->squashed) {

                moveToReady(woken_inst);

            } else {
                woken_inst->memDepReady = true;
            }
        }
    }

    inst_entry->dependInsts.clear();
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::squash(const TheISA::BlockID &squashed_num,
                                     ThreadID tid)
{
    ListIt squash_it = instList[tid].end();
    --squash_it;

    while (!instList[tid].empty() &&
           (*squash_it)->getBlockID() > squashed_num) {

        MemDepHashIt pos;

        uint64_t key = (*squash_it)->staticInst->getLSID() |
                       ((*squash_it)->getBlockID() << 5);

        DPRINTF(EdgeMemDepUnit, "Squashing inst"
                " [Bid:%lli][Iid:%lli][LSID:%x][key:%x]\n",
                (*squash_it)->getBlockID(),
                (*squash_it)->getInstID(),
                (*squash_it)->staticInst->getLSID(),
                key);

        for (pos = memDepHash.lower_bound(key);
             pos != memDepHash.upper_bound(key);
             ++pos) {

            if ((pos->second)->inst == (*squash_it)) {
                assert(pos != memDepHash.end());
                break;
            }

        }

        (*pos).second->squashed = true;

        (*pos).second = NULL;

#ifdef DEBUG
        MemDepEntry::memdep_erase++;
#endif
        memDepHash.erase(pos);
        instList[tid].erase(squash_it--);
    }
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::violation(DynInstPtr &store_inst,
                                        DynInstPtr &violating_load)
{
    panic("Unimplemented func: violation.\n");
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::issue(DynInstPtr &inst)
{
    panic("Unimplemented func: issue.\n");
}

template <class MemDepPred, class Impl>
inline typename EdgeMemDepUnit<MemDepPred,Impl>::MemDepEntryPtr 
EdgeMemDepUnit<MemDepPred, Impl>::findInHash(const DynInstPtr &inst)
{
    MemDepHashIt pos;

    uint64_t key = inst->staticInst->getLSID() | (inst->getBlockID() << 5);

    for (pos = memDepHash.lower_bound(key);
         pos != memDepHash.upper_bound(key);
         ++pos) {

        assert(pos != memDepHash.end());

        if (((pos->second)->inst) == inst) {

            return pos->second;
        }
    }
    // No entry is found
//    return pos->second;
    return NULL;
}

template <class MemDepPred, class Impl>
inline void
EdgeMemDepUnit<MemDepPred, Impl>::moveToReady(MemDepEntryPtr &woken_inst_entry)
{
    DPRINTF(EdgeMemDepUnit, "Adding instruction [sn:%lli] "
            "to the ready list.\n", woken_inst_entry->inst->seqNum);

    assert(!woken_inst_entry->squashed);

    woken_inst_entry->issued = true;

    iqPtr->addReadyMemInst(woken_inst_entry->inst);
}

template <class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::dumpLists()
{
    for (ThreadID tid = 0; tid < Impl::MaxThreads; tid++) {
        cprintf("Instruction list %i size: %i\n",
                tid, instList[tid].size());

        ListIt inst_list_it = instList[tid].begin();
        int num = 0;

        while (inst_list_it != instList[tid].end()) {
            cprintf("Instruction:%i\nPC:%#x\n[sn:%i]\n[tid:%i]\nIssued:%i\n"
                    "Squashed:%i\n\n",
                    num, (*inst_list_it)->readPC(),
                    (*inst_list_it)->seqNum,
                    (*inst_list_it)->threadNumber,
                    (*inst_list_it)->isIssued(),
                    (*inst_list_it)->isSquashed());
            inst_list_it++;
            ++num;
        }
    }

    cprintf("Memory dependence hash size: %i\n", memDepHash.size());

#ifdef DEBUG
    cprintf("Memory dependence entries: %i\n", MemDepEntry::memdep_count);
#endif
}

template<class MemDepPred, class Impl>
int64_t
EdgeMemDepUnit<MemDepPred, Impl>::findLastStore(DynInstPtr &inst, ThreadID tid)
{
    int producing_store;

    // Find the last store in its own block
    producing_store = inst->getLastStore();

    if (producing_store >= 0) {
        DPRINTF(EdgeMemDepUnit, "Find a prior store: [Bid:%lli][LSID:%i]!\n",
                inst->getBlockID(),
                producing_store);

        //Return the key of this store
        return (producing_store | (inst->getBlockID() << 5));
    }

    if (!inst->isBlockSpeculative()) {
        DPRINTF(EdgeMemDepUnit, "Find no prior store!\n");

        // This is the non-speculative block which means
        // it's the head of RoB, so just return a negative
        // flag indicating there's no prior store insts.
        return -1;
    }

    if (instList[tid].empty()) {
        // If instList is empty, no need to lookup.
        DPRINTF(EdgeMemDepUnit, "No mem ref in prior inst blocks,"
                " no dependence will be built.\n");
        // Hit this means no prior stores.
        return -1;
    }

    ListIt list_it = instList[tid].end();
    list_it--;

    do {
        // Find one inst in last block by iterating.
        // Inst List will have the youngest inst in tail and
        // the block id may not be adjacent to each other,
        // As a result ,
        // to judge whether it's an elder inst block or not, we
        // should use the 'less' operator.
        if ((*list_it)->getBlockID() < inst->getBlockID()) {

            DPRINTF(EdgeMemDepUnit, "Search last inst"
                    " block[Bid:%lli] for dependence.\n",
                    (*list_it)->getBlockID());

            if ((*list_it)->isStore()) {
                DPRINTF(EdgeMemDepUnit, "Find a prior store:"
                        " [Bid:%lli][LSID:%i]!\n",
                        (*list_it)->getBlockID(),
                        (*list_it)->staticInst->getLSID());

                return ((*list_it)->staticInst->getLSID() |
                        ((*list_it)->getBlockID() << 5));
            }

            return findLastStore(*list_it, tid);
        }

    } while ((list_it--) != instList[tid].begin());

    DPRINTF(EdgeMemDepUnit, "No mem insts is elder.\n");

    // Hit this means no prior stores.
    return -1;
}

template<class MemDepPred, class Impl>
void
EdgeMemDepUnit<MemDepPred, Impl>::findLastStores(DynInstPtr &inst,
        std::vector<uint64_t> &result, ThreadID tid)
{
    assert(inst->isLoad());

    if (instList[tid].empty()) {
        // If instList is empty, no need to lookup.
        DPRINTF(EdgeMemDepUnit, "No mem ref in prior inst blocks,"
                " no dependence will be built.\n");

        // Hit this means no prior stores.
        return;
    }

    ListIt list_it = instList[tid].end();
    list_it--;

    do {
        // Find one inst in last block by iterating.
        // Inst List will have the youngest inst in tail and
        // the block id may not be adjacent to each other,
        // As a result, we use operator 'less and equal' to find the
        // stores in the same block with smaller lsid and stores in
        // the elder blocks.
        //
        // @todo: Actually, there is an issue need to be addressed. So
        // far as right now, I assume that the memory references are
        // inserted in MemDepUnit in LSID order, so I didn't check the
        // stores in the same block to make sure it has a smaller LSID
        // than this load.
        if ((*list_it)->getBlockID() <= inst->getBlockID()) {

            DPRINTF(EdgeMemDepUnit, "Search last inst"
                    " block[Bid:%lli] for dependence.\n",
                    (*list_it)->getBlockID());

            if ((*list_it)->isStore()) {

                if ((*list_it)->getBlockID() == inst->getBlockID()) {
                    assert((*list_it)->staticInst->getLSID() <
                           inst->staticInst->getLSID());
                }

                DPRINTF(EdgeMemDepUnit, "Find a prior store:"
                        " [Bid:%lli][LSID:%i]!\n",
                        (*list_it)->getBlockID(),
                        (*list_it)->staticInst->getLSID());

                uint64_t key = ((*list_it)->getBlockID() << 5) |
                               (*list_it)->staticInst->getLSID();

                bool add_to_result = true;

                std::vector<uint64_t>::iterator it = result.begin();
                std::vector<uint64_t>::iterator end = result.end();

                // Because there may be multiple stores with the same
                // LSID, so we will exclude the duplicates.
                while (it != end) {
                    if (*it == key) {
                        add_to_result = false;
                    }
                    it++;
                }

                if (add_to_result) {
                    result.push_back(key);
                }
            }
        }

    } while ((list_it--) != instList[tid].begin());

    return;
}

template<class MemDepPred, class Impl>
bool
EdgeMemDepUnit<MemDepPred, Impl>::checkDependent(DynInstPtr &load_inst,
        DynInstPtr &store_inst)
{
    // This function can only be invoked in perfect mode.
    assert(isPerfect);
    assert(load_inst->isLoad() && store_inst->isStore());

    DPRINTF(EdgeMemDepUnit, "Checking dependence for "
            "load[Bid:%lli][Iid:%i][LSID:%i] and " 
            "store[Bid:%lli][Iid:%i][LSID:%i]\n",
            load_inst->getBlockID(),
            load_inst->getInstID(),
            load_inst->staticInst->getLSID(),
            store_inst->getBlockID(),
            store_inst->getInstID(),
            store_inst->staticInst->getLSID());

    if (!store_inst->preExeValid) {
        // The effective address and access size hasn't been set by a
        // pre-execute model to this store inst. This means that this
        // store is in the false-predicated path, so it will never
        // cause dependences to a load.
        return false;
    }

    if (store_inst->preExeFault || load_inst->preExeFault) {
        // One of the two memory references will generate a fault, so
        // we should respect the dependence in LSID order.
        return true;
    }

    if (store_inst->preExeNullified) {
        // This store has been nullified in the pre-execute model, so
        // it actually will never cause dependences to a load.
        return false;
    }

    if (!load_inst->preExeValid || load_inst->preExeNullified) {
        // The effective address and access size hasn't been set by a
        // pre-execute model to this load inst. This means that this
        // load is in the false-predicated path, so it will not
        // execute.
        // Here I assume this load will depend on any valid store
        // prior to it.
        // Moreover, if this load will be nullified in execution, I
        // assume it will depend on any valid store prior to it as
        // well.
        return true;
    }

    Addr load_addr = load_inst->preExeEffAddr;
    int load_size = load_inst->preExeAccSize;
    Addr store_addr = store_inst->preExeEffAddr;
    int store_size = store_inst->preExeAccSize;

    DPRINTF(EdgeMemDepUnit, "Checking pre-execute dependents for addr"
            " load:@%#x size: %i and store:@%#x size: %i\n",
            load_addr,
            load_size,
            store_addr,
            store_size);

    assert(load_size > 0 && store_size > 0);

    for (int offset = 0; offset < load_size; ++offset) {

        // Figure out the forwarding boudaries.
        bool store_has_lower_limit =
            (load_addr + offset) >= store_addr;
        bool store_has_upper_limit =
            (load_addr + offset) <
            (store_addr + store_size);

        if (store_has_lower_limit && store_has_upper_limit) {
            // One of the load byte is dependent upon this store.
            return true;
        }
    }

    return false;
}

